package cn.initcap.algorithm.graph.util;

import cn.initcap.algorithm.graph.Graph;
import cn.initcap.algorithm.graph.SparseGraph;

/**
 * 判断图中是否有环
 *
 * @author initcap
 * @date Created in 7/30/19 4:11 PM.
 */
public class CycleDetection {

    private Graph<Integer, Double> graph;
    private boolean[] visited;
    private boolean hasCycle = false;

    public CycleDetection(Graph graph) {

        this.graph = graph;
        visited = new boolean[graph.nodeSize()];
        for (int v = 0; v < graph.nodeSize(); v++) {

            if (!visited[v]) {
                if (dfs(v, v)) {
                    hasCycle = true;
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph g = new SparseGraph("algorithm/testG10.txt", false);
        CycleDetection cycleDetection = new CycleDetection(g);
        System.out.println(cycleDetection.hasCycle());
    }

    /**
     * 从顶点 v 开始，判断图中是否有环
     *
     * @param v
     * @param parent
     * @return
     */
    private boolean dfs(int v, int parent) {

        visited[v] = true;
        for (int w : graph.adj(v)) {
            if (!visited[w]) {
                if (dfs(w, v)) {
                    return true;
                }
            } else if (w != parent) {
                return true;
            }
        }
        return false;
    }

    public boolean hasCycle() {
        return hasCycle;
    }

}
